package bit2;

import java.util.*;
public class bitMain9 {

    public int[] elem;
    public int usedSize;

    public bitMain9() {
        this.elem = new int[10];//10个0
    }

    public void shiftDown(int parent,int len) {
        int child=parent*2+1;
        while (child<len){
            if(child+1<len&&this.elem[child]<this.elem[child+1]){
                child++;
            }
            if(this.elem[parent]<this.elem[child]){
                int tmp=this.elem[child];

                this.elem[child]=this.elem[parent];
                this.elem[parent]=tmp;
                parent=child;
                child=parent*2+1;
            }
            else {
                break;
            }
        }
    }

    //1 4 18 7 .....
    public void createBigHeap(int[] array) {
//把需要的数据 存放到elem当中 一会儿建堆的时候 直接操作 elem数组就可以了
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for (int i = (this.usedSize-1-1)/2; i >= 0 ; i--) {
            shiftDown(i,this.elem.length);
        }
    }
    public int poll(){
        if(this.usedSize==0){
            throw new RuntimeException("队列为空");
        }
        int ret=this.elem[0];
        this.elem[0]=this.elem[this.usedSize-1];
        this.usedSize--;
        shiftDown(0, elem.length);
        return ret;
    }
    public void heapSort(){
        int end=this.usedSize-1;
        while (end>0){
            int tmp=this.elem[0];
            this.elem[0]=this.elem[end];
            this.elem[end]=tmp;
            shiftDown(0,end);
            end--;
        }
    }
    public static int[] topK(int[] array){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        Scanner in=new Scanner(System.in);
        int k=in.nextInt();
        if(k> array.length){
            throw new RuntimeException("错误异常");
        }
        for (int i = 0; i < array.length; i++) {
            if(i<=k-1){
                queue.offer(array[i]);
            }
            else {
                if(array[i]> queue.peek()){
                    queue.poll();
                    queue.offer(array[i]);
                }
            }
        }
        int[] ret=new int[k];
        for (int i = 0; i < k; i++) {
            ret[i]= queue.poll();
        }
        return ret;
    }
    public static void shell(int[] array,int gap) {
        int j=0;
        for (int i = gap; i <= array.length-1; i++) {
            int tmp=array[i];
            for (j=i-gap;j>=0;j=j-gap){
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

    /**
     *
     * @param array
     */
    public static void shellSort(int[] array) {
        int gap = array.length-1;//3
        while (gap > 1) {
            shell(array,gap);
            gap = gap/2;//1
        }
        shell(array,1);
    }
    public static void insertSort(int[] array) {
        int j=0;
        for (int i = 0; i < array.length; i++) {
            int tmp=array[i];
            for (j=i-1;j>=0;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }
                else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue=new PriorityQueue<>(k,(o1,o2)->{
            return o2.get(0)+o2.get(1)-o1.get(0)-o1.get(1);
        });
        for (int i=0;i<Math.min(nums1.length,k);i++)
        {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                List<Integer> list=new ArrayList<>();
                if (queue.size()<k){
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    queue.offer(list);
                }
                else {
                    int tmp=queue.peek().get(0)+queue.peek().get(1);
                    if(nums1[i]+nums2[j]<tmp){
                        queue.poll();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        queue.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> list=new ArrayList<>();
        for (int i = 0; i < k&&!queue.isEmpty(); i++) {
            list.add(queue.poll());
        }
        return list;
    }
    public static void main(String[] args) {
        int[] array = {6,2,1,7,5};
        System.out.println(Arrays.toString(array));
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void main2(String[] args) {
        int[] array={10,8,100,78,126,30};
        bitMain9 Main9=new bitMain9();
        Main9.createBigHeap(array);
        Main9.heapSort();
        System.out.println(Arrays.toString(Main9.elem));
    }
    public static void main1(String[] args) {
        int[] array={10,8,100,78,126,30};
        int[] ret=topK(array);
        System.out.println(Arrays.toString(ret));
    }
}
